/*
 * @lc app=leetcode.cn id=743 lang=typescript
 *
 * [743] 网络延迟时间
 */

// @lc code=start

//  思路：Dijkstra
//  求起点到所有节点的最短距离，再求所有最短距离的最大值
//  参考：https://leetcode-cn.com/problems/network-delay-time/solution/wang-luo-yan-chi-shi-jian-by-leetcode-so-6phc/

//  复杂度：O(n2) O(n2)

function networkDelayTime(times: number[][], n: number, k: number): number {
    // 创建邻接矩阵
    const graph = Array.from(new Array(n), () => new Array(n).fill(Infinity))
    for (const t of times) {
        const x = t[0] - 1, y = t[1] - 1
        graph[x][y] = t[2]
    }
    // 创建备忘录dp
    const dist = new Array(n).fill(Infinity)
    // base
    dist[k - 1] = 0
    // 保证不重复遍历
    const used = new Array(n).fill(false)

    // 遍历图
    for (let i = 0; i < n; ++i) {
        let x = -1
        for (let y = 0; y < n; ++y) {
            // 没有用过 并且 初次遍历或者先找距离最小的，最有潜力的先遍历
            if (!used[y] && (x === -1 || dist[y] < dist[x])) {
                x = y
            }
        }
        used[x] = true
        // 找到与x相邻的点并计算最短距离
        for (let y = 0; y < n; ++y) {
            dist[y] = Math.min(dist[y], dist[x] + graph[x][y])
        }
    }

    const res = Math.max(...dist)
    return res === Infinity ? -1 : res
};
// @lc code=end

console.log(networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))
